from itertools import takewhile

def decompress(s):
    tokens = []
    for c in s:
        if len(tokens) == 0:
            tokens.append([c])
            continue

        if (str.isdigit(c) and str.isdigit(tokens[-1][-1])
            or str.isalpha(c) and str.isalpha(tokens[-1][-1])):
            tokens[-1].append(c)
        else:
            tokens.append([c])
    tokens = [''.join(x) for x in tokens]
    tokens = ['1'] + ['['] + tokens + [']']
    children = [None] * len(tokens)
    brothers = [None] * len(tokens)
    stack = []
    flag = False
    for i, token in enumerate(tokens):
        if i == 0:
            stack.append(i)
            continue

        if token == '[':
            flag = True
        elif token == ']':
            stack.pop()
        else:
            if flag:
                children[stack[-1]] = i
                stack.append(i)
                flag = False
            else:
                brothers[stack[-1]] = i
                stack[-1] = i

    def dfs_visit(u):
        if str.isalpha(tokens[u]):
            return tokens[u]
        res = ''
        child = children[u]
        brother = child
        while brother is not None:
            res += dfs_visit(brother)
            brother = brothers[brother]
        res = res * int(tokens[u])
        return res

    result = dfs_visit(0)
    return result


def decompress2(s):
    tokens = []
    for c in s:
        if len(tokens) == 0:
            tokens.append([c])
            continue

        if (str.isdigit(c) and str.isdigit(tokens[-1][-1])
            or str.isalpha(c) and str.isalpha(tokens[-1][-1])):
            tokens[-1].append(c)
        else:
            tokens.append([c])
    tokens = [''.join(x) for x in tokens]

    stack = []
    for token in tokens:
        if token != ']':
            stack.append(token)
        else:
            s_ = []
            while stack[-1] != '[':
                s_.insert(0, stack.pop())
            s_ = ''.join(s_)
            stack.pop()
            d_ = stack.pop()
            s_ = s_ * int(d_)
            stack.append(s_)
    result = ''.join(stack)
    return result

print(decompress('3[2[e]a2[b3[c]]d]'))
print(decompress('3[m2[c]]'))
print(decompress('11[3[2[e]a2[b3[c]]d]]'))

print(decompress2('3[2[e]a2[b3[c]]d]'))
print(decompress2('3[m2[c]]'))
print(decompress2('11[3[2[e]a2[b3[c]]d]]'))











